package com.wfm.niuke.huisu;

import com.wfm.common.TreeNode;
import java.util.ArrayList;
import java.util.List;

public class P剑指Offer34二叉树中和为某一值的路径 {
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
//    List<Integer> path = new ArrayList<>();
//    List<List<Integer>> res = new ArrayList<>();
//    public List<List<Integer>> pathSum(TreeNode root, int target) {
//        dfs(root,target);
//        return res;
//    }
//    void dfs(TreeNode root,int target){
//        if(root==null){
//            return;
//        }
//        path.add(root.val);
//        if(root.left==null&&root.right==null&&target-root.val==0){
//            res.add(new ArrayList(path));
//        }
//        dfs(root.left,target-root.val);
//        dfs(root.right,target-root.val);
//        path.remove(path.size()-1);
//    }


//    List<List<Integer>> res = new ArrayList<>();
//    List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> pathSum(TreeNode root, int target) {
//        List<List<Integer>> r = new ArrayList<>();
//        dfs(root);
//        for (int i = 0; i < res.size(); i++) {
//            List<Integer> integers = res.get(i);
//            int tmp = 0;
//            for (int j = 0; j < integers.size(); j++) {
//                tmp+=integers.get(j);
//            }
//            if(tmp==target){
//                r.add(integers);
//            }
//        }
//        return r;
//    }
//    void dfs(TreeNode root){
//        if(root==null){
//            return;
//        }
//        path.add(root.val);
//        if(root.left==null&&root.right==null){
//            res.add(new ArrayList<>(path));
//        }
//        dfs(root.left);
//        dfs(root.right);
//        path.remove(path.size()-1);
//    }

//    List<List<Integer>> res = new ArrayList<>();
//    List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> pathSum(TreeNode root, int target) {
//        List<List<Integer>> r = new ArrayList<>();
//        dfs(root,target);
//        return res;
//    }
//    void dfs(TreeNode root,int target){
//        if(root==null){
//            return;
//        }
//        path.add(root.val);
//        if(root.left==null&&root.right==null){
//            int tmp = 0;
//            for (int j = 0; j < path.size(); j++) {
//                tmp+=path.get(j);
//            }
//            if(tmp==target){
//                res.add(new ArrayList<>(path));
//            }
//        }
//        dfs(root.left,target);
//        dfs(root.right,target);
//        path.remove(path.size()-1);
//    }

    // 这题也是先一股脑进去，后判断条件
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return res;
    }
    void dfs(TreeNode root,int target){
        if(root==null) return;
        path.add(root.val);
        if(root.left==null&&root.right==null&&target-root.val==0){
            res.add(new ArrayList<>(path));
        }
        dfs(root.left,target-root.val);
        dfs(root.right,target-root.val);
        path.remove(path.size()-1);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指Offer34二叉树中和为某一值的路径().new Solution();
        TreeNode treeNode = TreeNode.generatorTreeNode("1,-2,3");
        solution.pathSum(treeNode,1);
    }
}